#include <iostream>
#include <vector>
#include <stack>
#include <stdlib.h>

using namespace std;
// 150. 逆波兰表达式求值
// 给定一个正确的逆波兰表达式（即后缀表达式）tokens，求该表达式的值（整数除法均为整除，不会出现除0情况）。
// tokens是已经拆分好的结果。
class Solution {
private:
    // 判断 str 串是否为运算符
    bool isoper(const string& str) {
        if(str.size() == 1 && (str[0] == '+' || str[0] == '-' || str[0] == '*' || str[0] == '/'))
            return true;
        else
            return false;
    }
public:
    int evalRPN(vector<string>& tokens) {
        int first, second, result;
        stack<int> st;  // 定义一个运算数栈
//        int i = 0;  // i遍历后缀表达式
        for(const string& s : tokens) { // 后缀表达式未扫描完时的循环
            if(isoper(s)) { // 当前字符是运算符字符串
                second = st.top(); st.pop();    // 出栈元素第2个操作数
                first = st.top(); st.pop();     // 出栈元素第1个操作数
                switch (s[0]) {
                    case '+':
                       result = first + second; // 计算+的结果
                       break;
                    case '-':
                        result = first - second; // 计算-的结果
                        break;
                    case '*':
                        result = first * second;    // 计算*的结果
                        break;
                    case '/':
                        result = first / second;    // 计算/的结果
                        break;
                }
                st.push(result); // 将计算结果result入栈
            }
            else    // 若当前字符未整数字符串
                st.push(atoi(s.c_str()));   // 转换为整数后进栈
        }
        return st.top();    // 返回栈顶元素

    }
};
int main() {
    vector<string> tokens1{"2","1","+","3","*"};
    std::cout << Solution().evalRPN(tokens1) << std::endl;  // 9

    vector<string> tokens2{"4","13","5","/","+"};
    std::cout << Solution().evalRPN(tokens2) << std::endl;  // 6

    vector<string> tokens3{"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
    std::cout << Solution().evalRPN(tokens3) << std::endl;  // 22
    return 0;
}
